package com.github.algorithm.tree;

/**
 * 场景: root节点未知, 非root节点保存left, right和parent节点, 且sub节点是无序的.
 * 思路:
 * 1. 先分别找出两个节点到root节点的长度
 * 2. abs(length1-length2)之后, 分头并进找到最近的公共父节点
 * @author Stephen
 * @date 2020/7/1 22:25
 */
public class BinaryTree<T extends Comparable<T>> {


    //找根节点到当前节点的长度
    public long getLength(TreeNode<T> node) {
        TreeNode<T> parent = node.getParent();
        long length = 0L;
        while (parent != null) {
            length++;
            parent = parent.getParent();
        }
        return length;
    }

    public TreeNode<T> findCommonParent(TreeNode<T> node1, TreeNode<T> node2) {

        long length1 = getLength(node1);
        long length2 = getLength(node2);

        TreeNode<T> iter1 = null;
        TreeNode<T> iter2 = null;
        long k = 0L;
        if (length1 >= length2) {
            TreeNode<T> temp = node1;
            while (k++ < length1-length2)
                temp = temp.getParent();
            iter1 = temp;
            iter2 = node2;
        }

        else {
            TreeNode<T> temp = node1;
            while (k++ < length2-length1)
                temp = temp.getParent();
            iter1 = node1;
            iter2 = temp;
        }

        //一起移动
        while (iter1 != iter2) {
            iter1 = iter1.getParent();
            iter2 = iter2.getParent();
        }
        return iter1;
    }

    public TreeNode<T> findCommonParent(TreeNode<T> root, TreeNode<T> node1, TreeNode<T> node2) {
        TreeNode<T> temp = root;
        while (temp != null)
            if (temp.getValue().compareTo(node1.getValue()) > 0
                    && temp.getValue().compareTo(node2.getValue()) > 0)
                temp = temp.getLeft();
            else if (temp.getValue().compareTo(node1.getValue()) < 0
                    && temp.getValue().compareTo(node2.getValue()) < 0)
                temp = temp.getRight();
            else return temp;
        return null;
    }
}
